Выполнила Титова Анастасия, 520 группа.
Разработать программу, которая обеспечивает работу с изображениями карточек игрового набора <<Геометрика>>. Реализовать ввод и отображение на экране изображений, сегментацию изображений на основе точечных и пространственных преобразований, выделение и распознавание изображений фигур на карточках (определить тип фигуры, количество вершин и выпуклость, в случае, если фигура является многоугольником).
В задание входят следующие задачи на изображениях разной сложности:
Обе задачи ставятся в двух вариантах: с белым фоном (#) и с пестрым фоном (&).
Сложность задач соответствует трём классам: Beginner, Intermediate, Expert.
В разработанной программе реализовано решение задачи класса Expert:
– для любой сложности изображения (для произвольного взаимного расположения карточек и типа фона).
Входом программы являются изображения в формате JPG. Выход программы: для первой задачи – исходное изображение с нанесенной на нём нумерацией карточек, для второй – разметкой результата маркерами PnC или Pn: P – многоугольник, n – число вершин многоугольника, C – выпуклый многоугольник
Алгоритм программы был отлажен и обучен на приложенном к заданию наборе из 7 изображений различной сложности в формате JPG. Сложность изображения определяется а) количеством карточек б) их взаимным расположением в) сложностью фона (белый или пёстрый)
Карточки хаотично расположены на фоне, цвет карточек – синий, на карточках изображены геометрические фигуры, а также предметы: циркули, транспортиры ластики, мелки и прочее.
import numpy as np
import cv2
import math
import PIL
from PIL import ImageFont, Image, ImageDraw
from skimage import data
from skimage import io
from skimage import color
from skimage import filters
from skimage import exposure
from skimage import feature
from skimage import restoration
from skimage import img_as_ubyte
from skimage import measure
from matplotlib import cm
from skimage import morphology as m
from matplotlib import pyplot as plt
from scipy import ndimage as ndi
from skimage.transform import (hough_line, hough_line_peaks, probabilistic_hough_line)
%matplotlib inline
def showim(image, cm=None): #Show image
fig = plt.figure(figsize = (13,13))
ax = fig.add_subplot(111)
ax.imshow(image, cmap=cm)
def draw_text(im4t, coords, text):
font = ImageFont.truetype("/usr/share/fonts/truetype/freefont/FreeSansBold.ttf",size=22)
draw = ImageDraw.Draw(im4t)
draw.text(coords, text,(255,255,0), font=font)
draw = ImageDraw.Draw(im4t)
Для реализации этой функции используются средства библиотеки skimage. В функцию в качестве аргументов передаются изображение и флаг: True - если изображение с пестрым фоном, False - если с белым. Изображение переводится в формат hsv (hue, saturation, value) и бинаризуется по экспериментально подобранным порогам. Задача создания маски - отделить фон и посторонние элементы на карточках от карточек и изображённых на них фигур. В случае белого фона, достаточно было подобрать подходящие пороги и воспользоваться морфологическими операциями skimage для удаления шума (была использована реализация функции удаления мелких отверстий remove_small_holes).
Для пёстрого фона, маска формировалась сложнее, итоговая маска является побитовым И следующих масок:
Итоговая маска, сформированная в результате выполнения функции, выводится на экран.
#Create mask for edge detection
#True - complex background, False - simple background
def create_mask(img, flag = False):
img_hsv = color.rgb2hsv(img)
if (flag):
mask1 = (img_hsv[:,:,0]>0.3) & (img_hsv[:,:,0]<0.7)
mask1 = m.remove_small_holes(mask1)
mask1 = m.remove_small_objects(mask1)
mask2 = ~(img_hsv[:,:,0]<0.2)
mask2 = m.remove_small_holes(mask2)
mask3= (img_hsv[:,:,1]>0.1)
mask3 = m.remove_small_holes(mask3)
mask4=mask1&mask2&mask3
else:
mask = (img_hsv[:,:,1]>0.3)&(img_hsv[:,:,0]>0.3)
mask4 = m.remove_small_holes(mask,min_size=50)
showim(mask4, 'gray')
return mask4
Для реализации этой функции используются средства библиотеки skimage. В функцию в качестве аргументов передаются путь изображения и флаг: True - если изображение с пестрым фоном, False - если с белым. Для подсчёта карточек реализовано выделение фигур, изображенных на карточках, и далее считается именно количество выделенных фигур. Выбор такого подхода основан на том, что а) выделение и разделение пересекающихся карточек по границам карточек не удалось (были реализованы и опробованы различные алгоритмы, в том числе рассматривалось применение distance transform и watershed алгоритмов) б) для выполнения задач класса сложности Intemediate и Expert необходимо выполнять выделение фигур в) между фигурами и карточками можно установить взаимно однозначное соответствие.
Функция считывает изображение в переменную, далее вызывается функция создания маски, отделяющей фон от карточек, описанная выше.
Изображение, переведённое в grayscale, передаётся в функцию canny, реализующую детектор границ Кэнни.
В реализации библиотеки skimage алгоритм имеет несколько основных этапов:
В результате работы алгоритма мы получаем изображение с границами фигур, изображённых на карточках, и некоторым шумом – границы предметов на карточках, которые не удалось убрать с помощью маски.
Далее производится ряд морфологических операций для уточнения границ и избавления от шума: дилатация для соединения контуров, удаление мелких объектов для удаления контуров посторонних предметов, далее области заполняются с помощью функции binary_fill_holes и, так как размер нужных нам областей значительно превосходит размер областей случайных контуров, можем убрать тот шум, которые не удалось удалить на предыдущих этапах.
Далее применяем эрозию для получения более четких границ областей, убираем остаточный шум и выделяем связные компоненты.
Для выделения и подсчета связных компонент используется функция label из библиотеки skimage. В этой реализации используются модификации алгоритмов выделения связных компонент, предложенные в статье Wu, KeshengOtoo, EkowShoshani, Arie Optimizing connected component labeling algorithms, 2005: https://escholarship.org/uc/item/7jg5d1zn
Далее для разметки карточек на изображении вызвается функция draw_text, описанная выше. Полученное изображение записывается в файл "marked_image1.jpg".
#Count cards by detecting figures
def count_cards(img_path, flag):
img = io.imread(img_path)
img_gray = color.rgb2gray(img)
#creating mask for edge detection
mask = create_mask(img, flag)
#Canny's edge detection
edges = feature.canny(img_gray, sigma=1.7, mask=mask)
#adjusting image: refining edges, erasing small edges/objects, filling small contours to remove them
edges2 = m.dilation(edges)
edges3 = m.remove_small_objects(edges2,150)
filled = ndi.binary_fill_holes(edges3)
newfin = m.remove_small_objects(filled, 300)
#erode objects to get sharpen edges
newfin= m.erosion(newfin,m.square(6))
#once again erasing small objects
newfin = m.remove_small_objects(newfin, 300)
#label areas and count them
labelled, num = measure.label(newfin, return_num=True)
showim(img)
showim(labelled)
im4t = Image.open(img_path)
for l in np.unique(labelled):
if(l>0):
i, j = np.where(labelled == l)
draw_text(im4t, (j[0]-15,i[0]), "№"+str(l))
im4t.save("marked_image1.jpg")
return num, newfin
Для реализации этой функции использовались средства библиотеки OpenCV. В качестве параметра в функцию передается изображение, полученное в результате выполнения функции count_cards.
Изображение приводится к формату, используемому в OpenCV, далее производится пороговая обработка изображения, и применяется функция findContours с режимом RETR_TREE(выделяет все контуры и восстанавливает полную иерархию) и методом аппроксимации CHAIN_APPROX_SIMPLE (сжимает горизонтальные, вертикальные и диагональные сегменты и оставляет только из конечные точки). Далее, для каждого контура мы применяем функцию approxPolyDP, которая использует алгоритм Рамера-Дугласа-Пекера, чтобы приблизить контур, некоторым контуром с меньшим числом точек. В ходе экспериментов, оптимальной была выбрана точность приблежения $0.017 * P$, где $P$ – периметр исходного контура.
За количество углов рассматриваемой фигуры примем количестов точек контура, полученного в результате аппроксимации. Рассмотрим взаимное расположение этих точек. Проанализировав различные характеристики контуров фигур с карточек набора, можем сделать вывод, что при любом положении карточки на плоскости расстояние между точками многоугольника с количеством вершин менее $10$ должно превосходить $12$. Однако в силу нечеткости границ, возникают "лишние" углы. Следовательно, обнаружив многоугольник с такими характеристиками, уменьшим количество его вершин на $1$. Удалять саму точку из контура не обязательно, т.к. это незначительно влияет на остальные характеристики. Далее для каждого контура находим его характеристики, которые будем использовать для определения свойств фигуры на карточке: периметр, площадь, отношение сторон прямоугольника, в который вписана фигура, и отношение площади области, ограниченной контуром, к площади выпуклой оболочке задающих его точек.
В ходе экспериментов, было обнаружено, что все фигуры с гладкой границой аппроксимируются не менее, чем $7$ точками, следовательно, все фигуры с меньшим количеством вершин можем определить как многоугольники. Далее, среди фигур с $7$ и более вершинами, разница между площадью области, ограниченной аппроксимированным контуром с меньшим количеством точек, и площадью области, ограниченной исходным контуром, превышает пороговое значение $168$ лишь у фигур с гладким контуром.
Далее проверяем выпуклость фигуры, ограниченной контуром, с помощью вычисления solidity -- отношение площади области, ограниченной контуром, к площади выпуклой оболочке задающих его точек. Для отсечения невыпуклых фигур был выбран порог $0.94$.
Однако было обнаружено, что в некоторых ракурсах, невыпуклая фигура с гладкой границей, аппроксимируемая $8$ вершинами, не удовлетворяет пороговому значению $168$. В качестве временного решения для определения данной фигуры было выбрано значение отношения сторон прямоугольника, в который вписана фигура. Т.к. в предложенном для отладки и обучения наборе было лишь $2$ невыпуклые фигуры, аппроксимируемые $8$ вершинами, при этом обладающие ярковыраженными различиями в протяженности. Для дальнейшего выделения фигуры с гладкой границей, для этого отношения был выбран порог $0.9$. Данный выбор признака не является оптимальным, но на момент отправления отчёта более эффективные признаки для классификации фигур установить не удалось.
В процессе определения характеристик фигур формируется результирующая строка "res", содержащая маркировку для карточки, в соответсвии с постановкой задачи. Далее строка передаётся в функцию draw_text, Полученное изображение записывается в файл "marked_image2.jpg".
#classify objects and mark them accordingly:
#P - if a polygon, n - number of vertices, C - if polygon is convex
def mark_cards(img, img_path):
#transferring to OpenCV format
cv_im = img_as_ubyte(img)
#open image for drawing text
im4t = Image.open(img_path)
#finding contours
ret,thresh = cv2.threshold(cv_im,0,255,0)
im2, contours, hierarchy = cv2.findContours(thresh,cv2.RETR_TREE,cv2.CHAIN_APPROX_SIMPLE)
for c in contours:
res = "" #resulting string variable
# approximate the contour
peri = cv2.arcLength(c, True)
approx = cv2.approxPolyDP(c, 0.017 * peri, True)
corners = len(approx)
#delete point if it is too close to the previous (if there are less than 10 vertices)
#we are not deleting the point itself from an array since it doesn't make much of a difference
#we are just decreasing the "corners" counter
for i, point in enumerate(approx):
if i > 0:
prev_i = i - 1
else:
prev_i = len(approx)-1
previous = approx[prev_i]
y1 = point.item(1) - previous.item(1)
x1 = point.item(0) - previous.item(0)
if ((corners<10) & (math.sqrt(x1**2 + y1**2)<12)):
corners = corners-1
#calcuating some contour properties for classification
perimeter = cv2.arcLength(c,True)
area = cv2.contourArea(c)
x,y,w,h = cv2.boundingRect(c)
aspect_ratio = float(w)/h
hull = cv2.convexHull(c)
hull_area = cv2.contourArea(hull)
solidity = float(area)/hull_area
areaCORN = cv2.contourArea(approx)
#all our non-polygons tend to have >=7 vertices, so if there are less than 7 verticies it is a polygon
if (corners<7):
res = "P"+res+ str(corners)
else:
#most of our non-polygons can be detected by the difference between their initial contour area and
#and area of a polygon, built on approximated vertices
if ((area-areaCORN < 168)):
res = "P"+res+ str(corners)
#checking for convexity
if(solidity>0.94):
if(res!=""):
res=res+"C"
else:
#However it is hard to distinguish non-convex polygon with 8 verticies and non-convex non-polygon
#whose contour was approximated with 8 vertices.
#In our case the ratio of width to height of bounding rect of the object helps to destinguish between these two.
if (corners==8)&(aspect_ratio>0.9):
res=""
draw_text(im4t, (approx[0].item(0)-18, approx[0].item(1)),res)
draw = ImageDraw.Draw(im4t)
im4t.save("marked_image2.jpg")
return
В примерах ниже программа выводит:
img_path = "./Obraztsy/IMG_9.jpg"
num, img = count_cards(img_path, True)
mark_cards(img, img_path)
print("Количество карточек на изображении:", num)
showim(cv2.cvtColor(cv2.imread("marked_image1.jpg"), cv2.COLOR_BGR2RGB))
showim(cv2.cvtColor(cv2.imread("marked_image2.jpg"), cv2.COLOR_BGR2RGB))
img_path = "./Obraztsy/IMG_4.jpg"
num, img = count_cards(img_path, False)
mark_cards(img, img_path)
print("Количество карточек на изображении:", num)
showim(cv2.cvtColor(cv2.imread("marked_image1.jpg"), cv2.COLOR_BGR2RGB))
showim(cv2.cvtColor(cv2.imread("marked_image2.jpg"), cv2.COLOR_BGR2RGB))
В ходе реализации было испробовано множество алгоритмов и методов обработки изображений. Была сделана попытка добавить этап предобработки изображения (нормализация гистаграммы яркости, медианный фильтр, билатеральный фильтр, использование гауссовой фильтрации (т.к. применяется в ходе выделения границ Кэнни, этот фильтр был убран)), однако не удалось подобрать метод, который бы давал улучшение на всех изображениях. Как было описано выше, в начале была произведена попытка разделить и посчитать карточки, основываясь на из собственных границах с использованием алгоритма distance transform. Также, в ходе освоения различных библиотек и подборов порогов бинаризации были опробованы различные методы вычисления порога (например, метод Оцу). Был проведён анализ множества характеристик контуров, для выделения тех, которые могли бы послужить основными признаками для классификации фигур.
Дальнейшее улучшение текущей реализации программы можно проводить в трёх направлениях: